//原文链接:
//@https://blog.csdn.net/ITSOK_123/article/details/124474449
//定制化队列
class Solution {
public:
    class myQueue{
    public:
        // 定义单调队列
        deque<int> que;
        //如果push的数值大于当前队列尾部元素的数值，那么就将队列尾部端的数值弹出，
        void push(int value){
            while(!que.empty() && value>que.back()){
                que.pop_back();
            }
            que.push_back(value);
        }
        //检查当前队首元素是否已经要滑出去
        void pop(int value){
            if(!que.empty() && value==que.front()){
                que.pop_front();
            }
        }
        int front(){
            return que.front();
        }
    };
    vector<int> maxSlidingWindow(vector<int>& nums, int k) {
        myQueue que;
        vector<int> res;
        //定义保存滑动窗口的队列
        for(int i=0;i<k;i++){
            que.push(nums[i]);
        }
        //第一次的队首元素必然是一个窗口最大值
        res.push_back(que.front());
        //窗口开始滑动，每次增加一个元素
        for(int i=k;i<nums.size();i++){
            que.pop(nums[i-k]);
            que.push(nums[i]);
            res.push_back(que.front());
        }
        return res;
    }
};

//优先队列存储键值对
vector<int> maxSlidingWindow(vector<int>& nums, int k) {
        //定义一个优先队列存储当前的窗口内的值及其下标
        priority_queue<pair<int,int>> que;
        vector<int> res;
        for(int i=0;i<k;i++){
            // 主义key与value的关系
            que.emplace(nums[i],i);
        }
        // 此时的队首元素必然是第一个窗口的最大值
        res.push_back(que.top().first);
        for(int i=k;i<nums.size();i++){
            //窗口尾部添加元素
            que.emplace(nums[i],i);
            //判断队首元素是否还在窗口内
            while(que.top().second<i-k+1){
                que.pop();
            }
            //队首元素是窗口内最大值
            res.push_back(que.top().first);
        }
        return res;
    }
	
// 分块计算前后缀值
 vector<int> maxSlidingWindow(vector<int>& nums, int k) {
        //将nums划分为大小为k个元素的不同组0...k-1,k...2k-1,...
        int n = nums.size();
        //保存每个值在窗口内的前缀和后缀中的最大值
        vector<int> prefix(n),suffix(n);
        for (int i = 0; i < n; ++i) {
            if(i%k==0) prefix[i]=nums[i];
			else prefix[i] = max(prefix[i-1],nums[i]);
        }
		for(int i=n-1;i>=0;i--){
			if(i==n-1 || (i+1)%k==0)	suffix[i] = nums[i];
			else suffix[i] = max(suffix[i+1],nums[i]);
		}
        vector<int> ans ;
        //每个元素在窗口内的最大值要么是最左边元素的后缀值，要么是最右边元素的前缀值
        // 无论这个滑动窗口是否跨越了分组
        for (int i = 0; i <= n-1-k+1; ++i) {
            ans.push_back(max(suffix[i],prefix[i+k-1]));
        }
        return ans;
    }
    }




